{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Split Into Subarrays With GCD Greater Than One"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #math #dynamic-programming #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #数学 #动态规划 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumSplits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使子数组最大公约数大于一的最小分割数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个由正整数组成的数组 <code>nums</code>。</p>\n",
    "\n",
    "<p>将数组拆分为&nbsp;<strong>一个或多个&nbsp;</strong>互相不覆盖的子数组，如下所示:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>数组中的每个元素都&nbsp;<strong>只属于一个&nbsp;</strong>子数组，并且</li>\n",
    "\t<li>每个子数组元素的 <strong>最大公约数</strong> 严格大于 <code>1</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回<em>拆分后可获得的子数组的最小数目。</em></p>\n",
    "\n",
    "<p><b>注意</b>:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>子数组的 <strong>最大公约数&nbsp;</strong>是能将子数组中所有元素整除的最大正整数。</li>\n",
    "\t<li>\n",
    "\t<p data-group=\"1-1\"><strong>子数组&nbsp;</strong>是数组的连续部分。</p>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [12,6,3,14,8]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 我们可以把数组分成子数组:[12,6,3] 和 [14,8]。\n",
    "- 12、6、3 的最大公约数是 3，严格大于 1。\n",
    "- 14 和 8 的最大公约数是 2，严格来说大于 1。\n",
    "可以看出，如果不拆分数组将使最大公约数 = 1。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [4,12,6,14]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong> 我们可以将数组拆分为一个子数组，即整个数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 2000</code></li>\n",
    "\t<li><code>2 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-split-into-subarrays-with-gcd-greater-than-one](https://leetcode.cn/problems/minimum-split-into-subarrays-with-gcd-greater-than-one/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-split-into-subarrays-with-gcd-greater-than-one](https://leetcode.cn/problems/minimum-split-into-subarrays-with-gcd-greater-than-one/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[12,6,3,14,8]', '[4,12,6,14]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 贪心，利用gcd的性质\n",
    "    def minimumSplits(self, nums: List[int]) -> int:\n",
    "        # 只有当目前gcd为1的时候，才切割开，并且重新计算gcd\n",
    "        cnt = 1\n",
    "        g = nums[0]\n",
    "        for val in nums:\n",
    "            g = math.gcd(g, val)\n",
    "            if g == 1:\n",
    "                cnt += 1\n",
    "                g = val\n",
    "\n",
    "        return cnt\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSplits(self, nums: List[int]) -> int:\n",
    "        cur = 0\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            cur = math.gcd(cur, num)\n",
    "            if cur == 1:\n",
    "                cur = num\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSplits(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        count = 1\n",
    "        for num in nums:\n",
    "            res = gcd(res, num)\n",
    "            if res == 1:\n",
    "                res = num\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSplits(self, nums: List[int]) -> int:\n",
    "        n, res, preGcd = len(nums), 1, nums[0]\n",
    "        for i in range(1, n):\n",
    "            curGcd = gcd(preGcd, nums[i])\n",
    "            if curGcd == 1:\n",
    "                res += 1\n",
    "                curGcd = nums[i]\n",
    "            preGcd = curGcd\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSplits(self, nums: List[int]) -> int:\n",
    "        # 只有当目前gcd为1的时候，才切割开，并且重新计算gcd\n",
    "        cnts = 1\n",
    "        g = nums[0]\n",
    "        for val in nums:\n",
    "            g = math.gcd(g,val)\n",
    "            if g == 1:\n",
    "                cnts += 1\n",
    "                g = val \n",
    "        return cnts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSplits(self, nums: List[int]) -> int:\n",
    "        cnts = 1\n",
    "        g = nums[0]\n",
    "        for val in nums:\n",
    "            g = math.gcd(g,val)\n",
    "            if g == 1:\n",
    "                cnts += 1\n",
    "                g = val \n",
    "        return cnts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSplits(self, nums: List[int]) -> int:\n",
    "        # 只有当目前gcd为1的时候，才切割开，并且重新计算gcd\n",
    "        cnts = 1\n",
    "        g = nums[0]\n",
    "        for val in nums:\n",
    "            g = math.gcd(g,val)\n",
    "            if g == 1:\n",
    "                cnts += 1\n",
    "                g = val \n",
    "        return cnts\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSplits(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        r = 0\n",
    "        while i < n - 1:\n",
    "            t = math.gcd(nums[i], nums[i + 1])\n",
    "            #print(f't={t}')\n",
    "            if t <= 1:\n",
    "                r += 1\n",
    "                i += 1\n",
    "                continue\n",
    "            j = i + 2\n",
    "            while j < n:\n",
    "                #print(f'i={i}, j={j}')\n",
    "                t = math.gcd(t, nums[j])\n",
    "                #print(f't={t}')\n",
    "                if t <= 1:\n",
    "                    r += 1\n",
    "                    i = j\n",
    "                    #print(f'i={i}')\n",
    "                    break\n",
    "                j += 1\n",
    "            i = j\n",
    "        if i >= n - 1:\n",
    "            r += 1\n",
    "\n",
    "        return r"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
